//class Solution
//{
//public:
//	int jump(vector<int>& nums)
//	{
//		int left = 0, right = 0, maxPos = 0, ret = 0, n = nums.size();
//		while (left <= right) 
//		{
//			if (maxPos >= n - 1) 
//			{
//				return ret;
//			}
//
//			for (int i = left; i <= right; i++)
//			{
//				maxPos = max(maxPos, nums[i] + i);
//			}
//			left = right + 1;
//			right = maxPos;
//			ret++;
//		}
//		return -1; 
//};




//class Solution
//{
//public:
//	int monotoneIncreasingDigits(int n)
//	{
//		string s = to_string(n); 
//		int i = 0, m = s.size();
//		
//		while (i + 1 < m && s[i] <= s[i + 1]) i++;
//		if (i + 1 == m) return n; 
//		
//		while (i - 1 >= 0 && s[i] == s[i - 1]) i--;
//		s[i]--;
//		for (int j = i + 1; j < m; j++) s[j] = '9';
//		return stoi(s);
//	}
//};



class Solution
{
public:
	int canCompleteCircuit(vector<int>& gas, vector<int>& cost)
	{
		int n = gas.size();
		for (int i = 0; i < n; i++) 
		{
			int rest = 0; 
			int step = 0;
			for (; step < n; step++)
			{
				int index = (i + step) % n; 
				rest = rest + gas[index] - cost[index];
				if (rest < 0) break;
			}
			if (rest >= 0) return i;
			i = i + step; 
		}
		return -1;
	}
};